package datastructure.sort;

import java.util.Arrays;

/**
 * 插入排序
 *
 * @author jack.wu
 * @version 1.0
 * @date 2020-03-24
 */
public class InsertSort {
    public static void main(String[] args) {
        int[] array = new int[]{5, 1, 9, -1, 4, 10};
        long startTime = System.currentTimeMillis();
        insertSort(array);
        long endTime = System.currentTimeMillis();
        System.out.println(Arrays.toString(array));
        System.out.println("耗时：" + (endTime - startTime));
    }

    /**
     * 插入排序
     * 有序表和无序表
     * @param array
     */
    private static void insertSort(int[] array) {
        // 认为i<1之前是有序表 i>=1是无序表
        for (int i = 1; i < array.length; i++) {
            // 定义一个目标数
            int insertVal = array[i];
            // 目标数的前一个索引
            int insertIndex = i - 1;
            while (insertIndex >= 0 && insertVal < array[insertIndex]) {
                // 如果目标数小于前面这个数 则把有序表向后移动
                array[insertIndex + 1] = array[insertIndex];
                // 直到有序数组最前面
                insertIndex--;
            }
            // 把目标数添加到适当位置
            array[insertIndex+1] = insertVal;
            System.out.println("第"+i+"次排序: "+Arrays.toString(array));
        }
    }
}
